<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>

  //封装哈希表类
  function HashTable(){
  //  属性
    this.storage = [] //整个哈希表
    this.count = 0 //哈希表的长度
    this.limit = 7 //初始哈希表的长度

  //  哈希函数
    //（1）将字符串转成比较大的数字：hashCode
    //（2）将大的数字hashCode压缩到数组范围（大小）之内
      HashTable.prototype.hashFun = function(str,size){
      //    1、定义hashCode变量
      var hashCode = 0

      //    2、霍纳算法，计算hashCode的值
      // str.charCodeAt():将字母转换成Unicode编码
      for(var i = 0;i < str.length;i++){
        hashCode = 37 * hashCode + str.charCodeAt(i)  //37为质数
      }

      //    3、取余操作
      var index = hashCode % size

      return index
    }

  //  方法：
  //  1、插入&修改操作
    HashTable.prototype.put = function(key,value){
    //  1、通过哈希函数根据key获取对应的index
      var index = this.hashFun(key,this.limit)

    //  2、根据index取出对应的bucket
      var bucket = this.storage[index]

    //  3、判断改bucket是否为null
      if(bucket == null){
          bucket = []
          this.storage[index] = bucket
      }

    //  4、判断是否是修改数据
      for(var i=0;i<bucket.length;i++){ //查看当前bucket中是否有该元素
          var tuple = bucket[i]
          if(tuple[0] == key){ //如果key相等，则修改数据
            tuple[1] = value
              return
          }
      }

    //  5、进行添加数据
      bucket.push([key,value])
      this.count += 1

    //  6、判断是否需要扩容
      if(this.count > this.limit * 0.75){ //当装填因子大于0.75时进行扩容
          // this.resize(this.limit * 2) //进行哈希表扩容，将哈希表的长度变为原来的两倍
          var newSize = this.limit * 2
          var newPrime = this.getPrime(newSize) //判断新长度是否为质数
          this.resize(newPrime)
      }

    }


  //  获取方法
      HashTable.prototype.get = function(key){
      //  1、根据key获取对应的index
          var index = this.hashFun(key,this.limit)

      //  2、根据index获取对应的bucket
          var bucket = this.storage[index]

      //  3、判单bucket是否为null
          if(bucket == null){
              return null
          }

      //  4、有bucket，那么就进行线性查找
          for(var i=0;i < bucket.length;i++){
              var tuple = bucket[i]
              if(tuple[0] == key){
                  return tuple[1]
              }
          }

      //  5、依然没有找到，那么返回null
          return null

      }

  //    删除方法
      HashTable.prototype.remove = function(key){
      //  1、根据可以获取对应的index
          var index = this.hashFun(key,this.limit)

      //  2、根据index获取对应的额bucket
          var bucket = this.storage[index]

      //  3、判读bucket是否为null
          if(bucket == null) return null

      //  4、有bucket，那么进行线性查找，并删除
          for(var i=0;i < bucket.length;i++){
              var tuple = bucket[i]
              if(tuple[0] == key){
                  bucket.splice(i,1) //执行删除
                  this.count--  //长度
                  return tuple[1]

              //    缩小容量
                  if(this.limit > 7 && this.count < this.limit * 0.25){
                      var newSize = Math.floor(this.limit / 2)
                      var newPrime = this.getPrime(newSize)
                      this.resize(newPrime)
                  }
              }
          }

      //  5、依然没有找到，那么返回null
          return null
      }

  //    判断哈希表是否为null
      HashTable.prototype.isEmpty = function(){
        return this.count == 0
      }

  //    获取哈希表中元素的个数
      HashTable.prototype.size = function(){
        return this.count
      }

  //    哈希表的扩容
      HashTable.prototype.resize = function(newLimit){
      //  1、保存旧的数组的内容
          var oldStorage = this.storage

      //  2、重置所有的属性
          this.storage = []
          this.count = 0
          this.limit = newLimit //新哈希表的长度

      //  3、遍历oldStorage所有的bucket
          for(var i = 0;i<oldStorage.length; i++){
          //    3.1、取出对应的bucket
              var bucket = oldStorage[i]

          //    3.2、判断bucket是否为null
              if(bucket == null){
                  continue
              }

         //    3.3、bucket中有数据，那么取出数据添加到新的哈希表中
              for(var x=0; x< bucket.length; x++){ //遍历获取bucket中的数据
                  var tuple = bucket[i]
                  this.put(tuple[0],tuple[1]) //将每一项数据添加到新的哈希表中
              }
          }

      }

      HashTable.prototype.isPrime = function(num){
          //  1、获取num的平方根
          var temp = parseInt(Math.sqrt(num)) //parseInt():转化为整数，Math.sqrt()获取平方根

          //  2、循环判断
          for(var i = 2;i<=temp;i++){
              if(num % i == 0){
                  return false
              }
          }

          return true

      }

      HashTable.prototype.getPrime = function(num){
        while(!this.isPrime(num)){ //判断是否是质数
            num++ //不是质数就+1，一直到找到质数为止
        }
        return num
      }

  }

</script>
</body>
</html>